package code.oldCode.feishuSpecializedTraining.binary_tree;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author 26029
 * @date 2025/3/14
 * @description
 */
public class MyBinaryTree6 {
    // 98. 验证二叉搜索树
    public boolean isValidBST(TreeNode root) {
        // 中序遍历：迭代
        if (root == null)
            return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        long prev = Long.MIN_VALUE, now;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            now = node.val;
            node = node.right;

            if (now <= prev)
                return false;
            prev = now;
        }
        return true;
    }

    public boolean isValidBST_(TreeNode root) {
        // 递归
        return isValidDFS(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidDFS(TreeNode root, long min, long max) {
        if (root == null)
            return true;
        if (root.val >= max || root.val <= min)
            return false;
        return isValidDFS(root.left, min, root.val) && isValidDFS(root.right, root.val, max);
    }

    // 530. 二叉搜索树的最小绝对差
    public int getMinimumDifference(TreeNode root) {
        if (root == null)
            return 0;
        Stack<TreeNode> stack = new Stack<>();
        int ans = Integer.MAX_VALUE;
        int prev = -1;
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (prev >= 0 && node.val - prev < ans) {
                ans = node.val - prev;
                // 剪一个小枝，感觉意义不大
                if (ans == 1)
                    return 1;
            }
            prev = node.val;
            node = node.right;
        }
        return ans;
    }

    // 501. 二叉搜索树中的众数
    public int[] findMode(TreeNode root) {
        // 有额外空间的做法：中序遍历
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        // 得到list开始找众数
        List<Integer> ans = new ArrayList<>();
        int count = 1, num = list.get(0);
        int max_count = count;
        ans.add(list.get(0));
        int len = list.size();
        for (int i = 1; i < len; i++) {
            int nowNum = list.get(i);
            if (nowNum == num) {
                count++;
            } else {
                num = nowNum;
                count = 1;
            }
            if (count > max_count) {
                max_count = count;
                ans.clear();
                ans.add(nowNum);
            } else if (count == max_count) {
                ans.add(nowNum);
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    private List<Integer> ans = new ArrayList<>();
    private int maxCount = 0, nowCount = 0;
    private int num = 0;

    public int[] findMode_(TreeNode root) {
        // 没有额外空间的morris遍历：前驱节点
        TreeNode node = root, prev = null;
        while (node != null) {
            // 如果没有左子，遍历自身，转向右子
            if (node.left == null) {
                handle(node.val);
                node = node.right;
                continue;
            }
            // 如果有左子，找到prev，没有连接则连接，转向左子，有连接则说明prev遍历过了，遍历自身，转向右子
            prev = node.left;
            while (prev.right != null && prev.right != node) {
                prev = prev.right;
            }
            if (prev.right == null) {
                prev.right = node;
                node = node.left;
            } else {
                prev.right = null;
                handle(node.val);
                node = node.right;
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    public void handle(int val) {
        if (val == num) {
            nowCount++;
        } else {
            nowCount = 1;
            num = val;
        }
        if (nowCount >= maxCount) {
            if (nowCount > maxCount) {
                ans.clear();
                maxCount = nowCount;
            }
            ans.add(val);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = null;
        root.right = new TreeNode(2);
        MyBinaryTree6 m = new MyBinaryTree6();
        System.out.println(Arrays.toString(m.findMode(root)));
    }
}
